package deepFirstSearch;

import java.util.ArrayList;
import java.util.List;

public class PacificAtlantic {
    //设置方向
    private static int[] direction = new int[]{1, 0, -1, 0, 1};

    private static boolean pacificFlag = false;
    private static boolean atlanticFlag = false;

    /**
     * LeetCode T417 太平洋大西洋水流问题
     *
     * 给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。
     *
     * 规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。
     *
     * 请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/pacific-atlantic-water-flow
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param args
     */
    public static void main(String[] args) {
        int[][] heights = new int[][]{
                {1,2,2,3,5},
                {3,2,3,4,4},
                {2,4,5,3,1},
                {6,7,1,4,5},
                {5,1,1,2,4}
        };
        pacificAtlantic(heights);

    }

    public static List<List<Integer>> pacificAtlantic(int[][] heights) {
        List<List<Integer>> ans = new ArrayList<>();
        if (heights.length == 0 || heights[0].length == 0){
            return ans;
        }
        for (int i = 0; i < heights.length; i++) {
            for (int j = 0; j < heights[0].length; j++){
                int[][] flag = new int[heights.length][heights[0].length];
                flag[i][j] = 1;
                dfs(heights, flag, i, j);
                if (pacificFlag && atlanticFlag){
                    List<Integer> list = new ArrayList<>();
                    list.add(i);
                    list.add(j);
                    ans.add(list);
                }
                pacificFlag = false;
                atlanticFlag = false;
            }
        }
        return ans;
    }

    public static void dfs(int[][] heights, int[][] flag, int m, int n){
        if (m == 0 || n == 0){
            pacificFlag = true;
        }
        if (m == heights.length - 1 || n == heights[0].length - 1){
            atlanticFlag = true;
        }
        //设置递归出口
        if (pacificFlag && atlanticFlag){
            return;
        }
        //进行递归操作
        for (int i = 0; i < 4; i++){
            int x = direction[i] + m;
            int y = direction[i + 1] + n;
            if (x >= 0 && y >= 0 && x < heights.length && y < heights[0].length && heights[x][y] <= heights[m][n] && flag[x][y] == 0 ){
                flag[x][y] = 1;
                dfs(heights, flag, x, y);
            }
        }
    }
    //逆向思维，找到可以从河流到达的地点
}
